/*
递归法翻转链表
1. 头插法初始化
2. 递归翻转
*/
#include <iostream>
using namespace std;

struct Node
{
	int data;
	Node* next = NULL;
	Node(int value):data(value){};
	Node(){};
};

//头插初始化链表,这个头结点有数据
Node* HeadInsert(Node* head,int arr[],int arrSize){
	head = NULL;
	for(int i = 0;i < arrSize;i++){
		Node* new_node = new Node(arr[i]);
		new_node->next = head;
		head = new_node;
	}
	return head;
}

//递归翻转
Node* RecursiveReverse(Node* head){
	if(head == NULL || head->next == NULL){
		return head;
	}
	else{
		Node* second = head->next;
		Node* new_head = RecursiveReverse(second);
		second->next = head;
		head->next = NULL;
		return new_head;
	}

}
//打印
void Print(Node* head){
	Node* cur = head;
	while(cur != NULL){
		cout<<cur->data<<"  ";
		cur = cur->next;
	}
	cout<<endl;
}

int main(int argc, char const *argv[])
{
	int arr[5] = {5,4,3,2,1};
	Node* head = new Node;
	head = HeadInsert(head,arr,5);
	Print(head);			//1，2，3，4，5
	Print(RecursiveReverse(head));		//5,4,3,2,1

	return 0;
}